Algoritmo de Shor

En computación cuántica, el algoritmo de Shor es un algoritmo cuántico para descomponer en factores un número N en tiempo O((log N)³) y espacio O(logN), así nombrado por Peter Shor.

El algoritmo de Shor es un procedimiento que permite encontrar factores de un número de una manera eficiente. La implementación de este algoritmo se puede llevar a cabo de manera clásica o utilizando circuitos cuánticos (que no han sido llevados a la práctica todavía). Esta última implementación es (por supuesto) la más conveniente cuando se desea encontrar el orden, un parámetro muy necesario a la hora de encontrar los factores primos de un cierto número.

Muchas criptografías de clave pública, tales como RSA, llegarían a ser obsoletas si el algoritmo de Shor es implementado alguna vez en una computadora cuántica práctica. Un mensaje cifrado con RSA puede ser descifrado descomponiendo en factores la llave pública N, que es el producto de dos números primos. Los algoritmos clásicos conocidos no pueden hacer esto en tiempo O((log N)^k) para ningún k, así que llegan a ser rápidamente poco prácticos a medida que se aumenta N. Por el contrario, el algoritmo de Shor puede romper RSA en tiempo polinómico. También se ha ampliado para atacar muchas otras criptografías públicas.

Como todos los algoritmos de computación cuántica, el algoritmo de Shor es probabilístico: da la respuesta correcta con alta probabilidad, y la probabilidad de fallo puede ser disminuida repitiendo el algoritmo.

El algoritmo de Shor fue aplicado en la práctica en 2001 por un grupo en IBM, que descompuso 15 en sus factores 3 y 5, usando una computadora cuántica con 7 qubits.